package com.zlk.algorithm.huawei.nowcoder.dp.string;

import java.util.Scanner;

/**
 * @program: algorithm
 * @ClassName HJ24
 * @description: dp 队列  子序列
 * @author: slfang
 * @create: 2024-12-23 14:36
 * @Version 1.0
 **/
public class HJ24 {

    // com.zlk.algorithm.algorithm.dynamicPlan.longestIncreasingSubsequence;
    // todo 二分优化
    //
    //  N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
    //  同学 K位  1——K 编号
    //           T1-Tk 身高
    //
    //  注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等
    //区间：转换题意找最长递增子序列

    public static int MAXN=3000;

    public static int n;

    //分析题目可得，其实就是求最长递增子序列的变种题目，只不过加了一个约束条件，需要左边递增右边递减的情况。
    //
    //1、先找到每一个位置i左侧的最长上升子序列长度left[i]
    // 2、再找到每一个位置i右侧的最长下降子序列长度right[i]
    // 3、然后求出所有位置的最长序列长度=左侧最长子序列长度+右侧最长子序列长度-1（因为该位置被算了两次，所以减1）
    // 4、然后用数目减去最长序列长度就是答案，需要出队的人数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            System.out.println(f(arr));
        }
    }

    private static int f(int[] arr) {
        int n = arr.length;
        //最长递增dp
        // 以i结尾最长递增自序列长度
        //  dp[i]
        int[] dp1 = new int[n];
        //最长递减dp
        int[] dp2 =new int[n];
        dp1[0]=1;//第一位就是递增或者递减
        for (int i = 0; i < n; i++) {
            //求i之前最长递增子序列长度
            dp1[i]=1;
            for (int j = 0; j <i ; j++) {
                if(arr[i]>arr[j]){
                    dp1[i] = Math.max(dp1[i],dp1[j]+1);
                }
            }
        }

        dp2[n-1] = 1;
        for (int i = n-1; i >=0 ; i--) {
            dp2[i] =1;
            for (int j = n-1; j >i ; j--) {
                if(arr[i]>arr[j]){
                    dp2[i] = Math.max(dp2[i],dp2[j]+1);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans,dp1[i]+dp2[i]);

        }
        return n-(ans-1);
    }


}
